package com.fjl.list.leetcode86;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/12 11:05
 */
/*
    给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    注：你应当 保留 两个分区中每个节点的初始相对位置。
*/
public class SplitLinkedList {
    public static void main(String[] args) {

    }

    /*
        在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，
        一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。
    */
    public ListNode partition(ListNode head, int x) {
        // 小于x的链表的虚拟头节点
        ListNode dummy1 = new ListNode(-1);
        // 大于等于x的链表的虚拟头节点
        ListNode dummy2 = new ListNode(-1);

        // 由p1,p2去往后走生成两个链表
        ListNode p1 = dummy1, p2 = dummy2;
        // 不直接对head进行遍历操作，由p进行遍历
        ListNode p = head;
        // 注意：任何头结点都不直接操作，而是重新赋值一个新的指针代替它们去操作

        while (p != null) {
            if (p.val < x) {
                p1.next = p;
                p1 = p1.next; //往后走，继续接后面的节点
            } else {
                p2.next = p;
                p2 = p2.next; //往后走，继续接后面的节点
            }
            // 不能直接让 p 指针前进，因为上面的p1.next = p;p2.next = p都是直接连接的p,如果不断开p后面的，那么新生成的两个链表还接着原始链表的数据
            // p = p.next
            // 断开原链表中的每个节点的 next 指针
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }

        // 合并两个链表
        p1.next = dummy2.next; // 如果上面直接p = p.next，那么这里就会形成环状链表

        return dummy1.next;
    }
}
